In most pipeline processors, conditional branch instructions are resolved in the execution (E) unit. Hence, there are several cycles of delay between the decoding of a conditional branch instruction and its execution/resolution. In an attempt to overcome the potential loss of these cycles, the decoder guesses as to which instructions to decode next. Many pipeline processors classify branches according to the instruction field. When a branch is decoded, the outcome of the branch is predicted, based on its class.
In known computing systems, the reduction of branch penalty is attempted through the use of history focussed on instruction prefetching. Branch history tables (BHT) utilize the address of the instruction stream being prefetched for accessing a table. If a taken branch were previously encountered at that address, the table indicates so and, in addition, provides the target address of the branch on its previous execution. This target address is used to redirect instruction prefetching because of the likelihood that the branch will repeat its past behavior. The advantage of such an approach is that it has the potential of eliminating all delays associated with branches. There are, however, delays due to incorrect prediction of branches and delays due to cache access time for branch targets. The size of the BHT needs to be fairly large to reach a guessing accuracy on the order of 80%. The table has to contain a large number of entries to approach such accuracy, particularly for commercial environments. In addition the entries are wide, because they include a match field for comparison with the instruction address (used to access the table) and the full target address.
There are several instruction prefetching mechanisms known in the art, each having certain advantages and disadvantages. U.S. Pat. No. 3,559,183 to Sussenguth, which patent is assigned to the assignee of the present invention, sets forth an instruction prefetching mechanism utilizing a BHT. There is apparatus for recognizing the occurrence of a particular instruction in a stream of instructions and then modifying that stream of instructions. A fetch register for receiving instructions from a main memory is provided. A prefetch sequence control register containing the address of a particular instruction, as well as the address of the next instruction to be fetched is also provided. The comparison is continuously made between the instruction address in the fetch register and in the prefetch sequence control register. Upon noting an equality between these two, the second address from the prefetch sequence control register is transferred to the fetch register and the instruction extracted from memory. Means are also provided for inhibiting this operation and providing an address from a related register to the fetch register upon the occurrence of an equality between the address in the prefetch sequence control register and another related register.
U.S. Pat. No. 4,200,927 to Hughes et al, which patent is assigned to the assignee of the present invention, sets forth a multi-instruction stream branch processing mechanism which predicts outcomes of additional branch instructions based on the instruction field.
U.S. Pat. No. 3,940,741 to Horikoshi et al sets forth an information processing device for processing instructions including branch instructions. A route memory is provided for storing branch target addresses of a plurality of branch instructions and branch target instructions in corresponding relationship to the branch target addresses, and the route memory is referenced by the address in a given instruction, whereby the branch target instruction at the corresponding branch target address is read out. That is, the Horikoshi et al patent utilizes the address of the target of the branch instruction for prediction purposes. Since a plurality of different branch instructions may have the same branch target address, it is seen that the prediction of the outcome of a given branch instruction may be based on the outcome of a different branch instruction.
According to the present invention, a method and apparatus of predicting the outcome of a conditional branch instruction based on the previous performance of the branch, rather than on the instruction field is set forth. That is, the prediction is based on the address of the branch instruction itself, and not on the address of the target of the branch instruction. The prediction of the outcome of a conditional branch instruction is performed utilizing a table that records the history of the outcome of the branch at a given memory location. A decode-time history table (DHT) is utilized rather than a branch history table (BHT). The DHT attempts to guess only the outcome of a conditional branch instruction, but not its target address. Thus, it can only be used to guess the branch outcomes at decode time when the target address is available. During the decoding of a conditional branch instruction, a table is accessed using its memory address or some portion of the branch instruction itself. The table records the history of the outcome of the branch at this memory location up to a congruence of the table size. A combinational circuit determines the guess (taken or not taken) from the branch history as provided by the table. A simple version of this mechanism is to remember only the last outcome of every branch location. In this case, the output from the table is directly used as the guess. If the table indicates the branch was taken or fell through the last time, the prediction is to guess the branch successful or unsuccessful, respectively. The table is updated to always reflect the branch outcomes on their last execution. The table is initialized to provide a default guess. In contrast to the BHT, the DHT is accessed during the decode-cycle of the instruction (stage II of FIG. 1) and predicts only the branch outcomes (not target address). It is intended only to increase branch guessing accuracy, not to provide the address of targets for prefetching.